#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
       int diff = INT_MAX;
       int ans = 0;
        
       //sort the input data
       sort(num.begin(), num.end());
       for (int i = 0; i < num.size()-2; i++) {
           for (int j = i + 1, k = num.size()-1; j < k; ) {
                  int sum = num[i] + num[j] + num[k];
                  //cout << i << " " << j << " " << k << " " << sum  << " " << target << " " << diff << endl;
                  if (sum > target ) {
                      if (sum - target < diff) {
                          diff = sum - target;
                          ans = sum;
                      }
                      k--;
                      continue;   
                  } 

                  if (sum < target ) {
                      if (target - sum < diff) {
                          diff = target - sum;
                          ans = sum;
                      }
                      j++;
                      continue;
                  } 

                  if (sum == target) return sum;
           }
       }

       return ans;
    }
};

//add a better version
class Solution2 {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int ans;
        int dis = 100000000;
           for (int i = 0; i < num.size()-2; i++) {
            int j, k;            
            for (j = i+1, k = num.size()-1; j < k; ) {
                int sum = num[i] + num[j] + num[k];
                if (abs(sum-target) < dis) {ans = sum; dis = abs(sum-target);}
                if (sum == target) return sum;
                else if (sum < target) j++;
                else if (sum > target) k--;   
            }
        }       
        return ans;        
    }
};

//test in online judge http://www.leetcode.com/onlinejudge, but fail in the judge large now due to time limit exceed.         
int main(int argc, char **argv)
{
    Solution mySolution;
    //int input[] = {-1, 2, 1, -4};
    //int input[] = {0,2,1,-3}; 
    int input[] = {0,1,2};
    vector<int> test;
    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        test.push_back(input[i]);
    }

    int result = mySolution.threeSumClosest(test, 3);
    cout << result << endl;

    return 0;
}
